A designer using a computer aided design (CAD) computational system will typically approach the design of a free form geometric object (such as a surface) by first specifying prominent and/or necessary subportions of the geometric object through which the object is constrained to pass. Subsequently, a process is activated for generating the geometric object that conforms to the constraining subportions provided. In particular, such subportions may be points, curves, surfaces and/or higher dimensional geometric objects. For example, a designer that designs a surface may construct and position a plurality of curves through which the intended surface must pass (each such curve also being denoted herein as a “feature line” or “feature curve”). Thus, the intended surface is, in general, expected to have geometric characteristics (such as differentiability and curvature) that, substantially, only change to the extent necessary in order to satisfy the constraints placed upon the surface by the plurality of curves. That is, the designer expects the generated surface to be what is typically referred to as “fair” by those skilled in the art. Thus, the designer typically constructs such feature curves and positions them where the intended surface is likely to change its geometric shape in a way that cannot be easily interpolated from other subportions of the surface already designed.
As a more specific example, when designing containers such as bottles, an intended exterior surface of a bottle may be initially specified by subportions such as:
(a) feature curves positioned in high curvature portions of the bottle surface, and
(b) surface subareas having particular geometric characteristics such as having a shape or contour upon which a bottle label can be smoothly applied. Thus, the intention of a bottle surface designer is to construct a bottle design that satisfies his/her input constraints and that is also fair. Moreover, the designer may desire to generate holes for handles, as well as, e.g., ergonomic bottle grips by deforming various portions of the bottle surface and still have the bottle surface fair.
There has heretofore, however, been no CAD system wherein a designer (or more generally, user) of geometric objects can easily and efficiently express his/her design intent by inputting constraints and having the resulting geometric object be fair. That is, the designer/user may encounter lengthy delays due to substantial computational overhead and/or the designer/user may be confronted with non-intuitive geometric object definition and deformation techniques that require substantial experience to effectively use. For example, many prior art CAD systems provide techniques for allowing surfaces to be designed and/or deformed by defining and/or manipulating designated points denoted as “control points.” However, such techniques can be computationally expensive, non-intuitive, and incapable of easily deforming more than a local area of the surface associated with such a control point. Additionally, some prior art CAD systems provide techniques for defining and/or deforming surfaces via certain individually designated control vectors. That is, the direction of these vectors may be used to define the shape or contour of an associated surface. However, a designer's intent may not easily correspond to a surface design technique using such control vectors since each of the control vectors typically corresponds to only a single point of the surface isolated from other surface points having corresponding control vectors. Thus, such techniques are, at most, only able to deform an area of the surface local to such points having corresponding control vectors.
Additionally, such prior art CAD systems may also have difficulties in precisely performing blending and trimming operations. For example, two geometric objects intended to abut one another along a common boundary may not be within a insufficient tolerance to one another at the boundary. That is, there may be sufficiently large gaps between the geometric objects that the boundary may not be considered “water tight,” which may be problematic in certain machining operations and other operations like Boolean operations on solids.
Prior art discloses techniques for generating multisided surface patches for geometric modeling. Such techniques are disclosed in U.S. Pat. No. 7,236,167 filed Oct. 20, 2003 by Lee et. al. which is fully incorporated herein by reference. Surfaces resulting from such techniques are able to represent N-sided object space surfaces (also referred to as NSS herein) for substantially all reasonable values for the number N (e.g., N≦20), wherein N is the number of boundary curves of the resulting surface (which is sometimes referred to as a “patch”). As an illustrative example, FIG. 45 shows a pentagon 3009 in parametric space, wherein each of its five sides is mapped into a corresponding portion of the boundary of the surface 3011 in object space, and the interior of the pentagon 3009 maps into the interior of the surface 3011 so that this interior smoothly meets this boundary. Moreover, various continuity constraints and/or smooth transitions across the boundaries between two or more such object space patches 3011 may be imposed as one skilled in the art will understand. Furthermore, there are various computational methods for expressing NSS.
Assuming an NSS surface is represented by a polynomial (and accordingly, its boundary curves are also representable by polynomials), the polynomial degree of NSS is important in that the higher degree, the greater flexibility to generate, e.g., desired curves and/or contoured surfaces. However, such flexibility comes at a price; e.g., geometric objects generated from high degree polynomial mappings are computationally expensive to generate and manipulate. Additionally, such high degree polynomial mappings can also affect the precision of various computations, e.g., due to the accumulation of computational errors. Accordingly, many (if not most) commercially successful geometric modelers limit the polynomial degree of the curves, surfaces and/or solids that they generate and manipulate to be below a predetermined value. For example, the geometric modeler by ACIS™ uses polynomials having a maximum of degree 25, and the geometric modeler by Rhino™ uses polynomials having a maximum of degree 32. Accordingly, when a geometric object representation is desired to be imported into such a commercial geometric modeler, it is very desirable for the object representation to have as low a polynomial degree as possible, and certainly below the maximum polynomial degree for which the target geometric modeler has been tested for reliability and accuracy. In particular, if the polynomial degree of the geometric object is imported directly into such a modeler, and the object's degree is above such the maximum recommended degree for the modeler, unexpected results may occur, e.g., the modeler may crash, an unacceptable build up computational errors may occur, and/or very lengthy processing times may be experienced, or even worse, undetected errors/inaccuracies may be incorporated into a geometric model generated by the modeler. Alternatively, prior to be imported, a geometric object having a representation of a too high degree may be converted into, e.g., a plurality of lower degree objects that are acceptable to the target modeler such that when these lower degree objects are combined, they approximate the original high degree object. However, such a conversion presents its own set of difficulties. In particular, there may be both computational efficiency difficulties and possibly difficulties maintaining certain tolerances in the target modeler. Moreover, there is very likely to be inaccuracies in the conversion process. For instance, the speed of computation in downstream processes within such a target modeler after such a conversion of a geometric object may grow greater than linearly with the degree of the object representation being converted. For example, a geometric object having representation with degree 50 may, when converted to, e.g., a plurality of 25 degree approximations subsequently require, e.g., four to five times the computational time that a geometric object represented by a polynomial representation of 25 degrees.
Accordingly, it would be very desirable to have a CAD system that includes one or more geometric design techniques for allowing CAD designers/users to more easily, efficiently and precisely design geometric objects. Further, it would be desirable to have such a system and/or computational techniques for graphically displaying geometric objects, wherein there is greater user control over the defining and/or deforming of computational geometric objects, and in particular, more intuitive global control over the shape or contour of computationally designed geometric objects. Additionally, it would be desirable to provide surfaces that smoothly blend into one another, wherein the surface representations have a low polynomial degree.
Moreover, one important quality of a surface is its smoothness. However, it is nontrivial to quantitatively measure what is meant by “smoothness”. For example, a know technique to measure the smoothness at a join of two surfaces is to use the continuity of the derivatives of the surface generating functions for those two surfaces. However, this measure of smoothness does not always work for parametric functions used in design. For instance, sometimes two functions can form a smooth curve or surface while their derivatives do not agree at a joint between the curves or surfaces. On the other hand, there could be a sharp cusp even if the derivatives are the same. In order to describe “smoothness”, certain terms are used in the art. In particular, various continuity criteria are used to describe smoothness. More precisely, let there be two parametric curves f(u) and g(v), where u and v are in the intervals [a,b] and [m,n], respectively. For describing the smoothness of a join of these curves, consider the “right-end” of curve f(u), i.e., f(b), and the “left-end” of curve g(v), i.e., g(m). If f(b)=g(m), we say curves f and g are C0 continuous at f(b)=g(m). If for all i<=k, the ith derivatives at f(b) and g(m) are equal, we shall say that the curves are Ck continuous at point f(b)=g(m).
Curvature is another measure that can be used to evaluate the smoothness between curves (and eventually surfaces). In particular, for a parametric function ƒ the curvature is defined byk=|ƒ′(t)×ƒ″(t)|/|ƒ′(t)|3  (A1)
If the curvatures of curves at a join thereof are equal, we will say they are curvature continuous at the join. Intuitively, two curves are curvature continuous if the turning rate is the same at the join; however, the second derivatives of these curves may not be the same at the join. In other words, curvature continuity is not always C2 continuity with parametric functions. For example, the following curve consists of two parabolic segments:f(u)=(u,−u2) and g(v)=(v,v2),where the left curve f and the right curve g have domains [−1,0] and [0,1], respectively. Consider the continuity of the two curves at the origin where they join, i.e.,f′(u)=(1,−2u)f″(u)=(0,−2)g′(v)=(1,2v)g″(v)=(0,2)Since f′(0)=g′(0)=(1, 0), these two curves are C1 continuous at the origin. However, since f″(0)=(0, −2) is not equal to g″(0)=(0, 2), they are not C2 continuous at the origin. In fact, f″(u) points to the south while g″(u) points to north, and both are constant. Therefore, when a moving point crosses the origin from one curve to the other, the second derivative changes its direction abruptly. However, the curvature of f(u) is kf=2/(1+4u2)1.5 and the curvature of g(v) is kg=2/(1+4v2)1.5. Accordingly, the two curve segments are curvature continuous at the join. Thus, we see that two curve segments may be C1 and curvature continuous, but not C2 continuous.
Consider yet another simple example. Letf(u)=A+u(B−A)g(v)=B+v(C−B)where A, B and C are three collinear points as shown in FIG. 1.
The functions f(u) and g(v) are obviously C0 continuous at the join B. Is it C1 continuous? We have:f′(u)=B−A g′(v)=C−B 
Clearly, f′(u)=B−A is not equal to g′(v)=C−B, for most values of A, B, and C. Consequently such line segments are, in general, not C1 continuous at B.
This poses a problem for parametric forms that is not seen in explicit forms where the derivative is a scalar—the slope. It is a result of the derivative being a vector with both magnitude and direction. If we replace the direction vectors B−A and C−B with unit-length vectors and change the domain of parameters u and v, this problem will disappear. That is, the above equations are re-parameterized to the following:F(u)=A+u(B−A)/|B−A|G(v)=B+v(C−B)/|C−B|where uε[0, |B−A|] and vε[0, |C−B|]. Now, since we have F′ (u)=G′ (v) equal to the unit-length vector in the direction of A to C, the line segments are C1 continuous. Thus, re-parameterizing the curve segments overcomes the problem.
Many C1 continuous curves are curvature continuous, but they are not C2 continuous at their join(s); some of them may not even be twice differentiable. However, these curves can appear smooth at the join(s), and having a smooth join is an important feature of computational design.
Therefore, we introduce the notion of Geometric Continuity defined in the following:
Two curve segments are said to be Gk geometric continuous (and have Gk Geometry Continuity) at their join if and only if there exist two parameterizations, one for each curve segment, such that all ith derivatives, i≦k, agree at the join.
Reference: Hoschek and Lasser.
                The idea of Gn geometric continuity (n−1) may be extended to surfaces as follows: two surfaces are Gn geometric continuous at a join thereof if and only if for each point of the join of the two surfaces, each curve on the surfaces that crosses the join at the point is Gn geometric continuous. Note that in the disclosure hereinbelow a surface (S) is described as being a Gn surface or Gn continuous when there is Gn geometric continuity for each joined pair of surfaces in S. Moreover, when there is no ambiguity, the surface S may be simply referred to as a “Gn surface”.        G2 geometric continuity is highly desirable for creating smoothness in design because it makes surfaces with smooth reflections and improves fluid flow among other advantages.        Therefore it would be desirable to have a computationally effective and efficient technique for describing “smoothness”, and in particular, using such a technique for generating designs of objects whose composite surfaces are visually smoother than typically provided by the prior art.        